import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Author: 笨蛋超人不会飞
 * Date:  21:48
 */
public class question_131 {
}
//分割回文串，采用回溯的算法
class Solution_131 {
//    定义一些全局的变量
    private List<List<String>> result = new ArrayList<>();
//    作为中间存储的工具
    private List<String> temp=new ArrayList<>();
//    用二维数组来记录每一个子串是否是回文的子串
    boolean f[][];


    public List<List<String>> partition(String s) {
        int len =s.length();
        f=new boolean[len][len];
//        先让数组f值都是true
        for (int i = 0; i < len; i++) {
            Arrays.fill(f[i],true);
        }
        for (int i = len-1; i >=0;i--) {
            for (int j = i+1; j <len ; j++) {
                f[i][j]=(s.charAt(i)==s.charAt(j)&&f[i+1][j-1]);
            }
        }
        dfs(s,0);
        return result;

    }

    private void dfs(String s, int i) {
        int n=s.length();
        if(i==n){
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int j =i; j <n ; j++) {
            if(f[i][j]){
                //当前分割的以index i开头，以j结尾的字符串是回文串的话，递归下去才有意义
                temp.add(s.substring(i,j+1));
                dfs(s,j+1);
                //移除最后一个，也就是递归之前加进来的那个，还原了原始的中状态
                temp.remove(temp.size()-1);
            }
        }
    }


}